Search Results

Documents authored by Grochow, Joshua A.

Document
DOI: 10.4230/LIPIcs.ITCS.2024.31
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups

Authors: Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, and Chuanqi Zhang

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We study the complexity of isomorphism problems for d-way arrays, or tensors, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. These problems arise naturally in statistical data analysis and quantum information. We study two types of complexity-theoretic questions. First, for a fixed action type (isomorphism, conjugacy, etc.), we relate the complexity of the isomorphism problem over a classical group to that over the general linear group. Second, for a fixed group type (orthogonal, unitary, or symplectic), we compare the complexity of the isomorphism problems for different actions. Our main results are as follows. First, for orthogonal and symplectic groups acting on 3-way arrays, the isomorphism problems reduce to the corresponding problems over the general linear group. Second, for orthogonal and unitary groups, the isomorphism problems of five natural actions on 3-way arrays are polynomial-time equivalent, and the d-tensor isomorphism problem reduces to the 3-tensor isomorphism problem for any fixed d > 3. For unitary groups, the preceding result implies that LOCC classification of tripartite quantum states is at least as difficult as LOCC classification of d-partite quantum states for any d. Lastly, we also show that the graph isomorphism problem reduces to the tensor isomorphism problem over orthogonal and unitary groups.
Cite as

Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, and Chuanqi Zhang. On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 31:1-31:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2024.31,
  author =	{Chen, Zhili and Grochow, Joshua A. and Qiao, Youming and Tang, Gang and Zhang, Chuanqi},
  title =	{{On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{31:1--31:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.31},
  URN =		{urn:nbn:de:0030-drops-195595},
  doi =		{10.4230/LIPIcs.ITCS.2024.31},
  annote =	{Keywords: complexity class, tensor isomorphism, polynomial isomorphism, group isomorphism, local operations and classical communication}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.4
On the Algebraic Proof Complexity of Tensor Isomorphism

Authors: Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, and Adrian She

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
The Tensor Isomorphism problem (TI) has recently emerged as having connections to multiple areas of research within complexity and beyond, but the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, TI (or rather, proving that two tensors are non-isomorphic) lends itself very naturally to algebraic and semi-algebraic proof systems, such as the Polynomial Calculus (PC) and Sum of Squares (SoS). For its combinatorial cousin Graph Isomorphism, essentially optimal lower bounds are known for approaches based on PC and SoS (Berkholz & Grohe, SODA '17). Our main results are an Ω(n) lower bound on PC degree or SoS degree for Tensor Isomorphism, and a nontrivial upper bound for testing isomorphism of tensors of bounded rank. We also show that PC cannot perform basic linear algebra in sub-linear degree, such as comparing the rank of two matrices (which is essentially the same as 2-TI), or deriving BA = I from AB = I. As linear algebra is a key tool for understanding tensors, we introduce a strictly stronger proof system, PC+Inv, which allows as derivation rules all substitution instances of the implication AB = I → BA = I. We conjecture that even PC+Inv cannot solve TI in polynomial time either, but leave open getting lower bounds on PC+Inv for any system of equations, let alone those for TI. We also highlight many other open questions about proof complexity approaches to TI.
Cite as

Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, and Adrian She. On the Algebraic Proof Complexity of Tensor Isomorphism. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 4:1-4:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{galesi_et_al:LIPIcs.CCC.2023.4,
  author =	{Galesi, Nicola and Grochow, Joshua A. and Pitassi, Toniann and She, Adrian},
  title =	{{On the Algebraic Proof Complexity of Tensor Isomorphism}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{4:1--4:40},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.4},
  URN =		{urn:nbn:de:0030-drops-182748},
  doi =		{10.4230/LIPIcs.CCC.2023.4},
  annote =	{Keywords: Algebraic proof complexity, Tensor Isomorphism, Graph Isomorphism, Polynomial Calculus, Sum-of-Squares, reductions, lower bounds, proof complexity of linear algebra}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.19
Matrix Multiplication via Matrix Groups

Authors: Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, and Chris Umans

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
In 2003, Cohn and Umans proposed a group-theoretic approach to bounding the exponent of matrix multiplication. Previous work within this approach ruled out certain families of groups as a route to obtaining ω = 2, while other families of groups remain potentially viable. In this paper we turn our attention to matrix groups, whose usefulness within this framework was relatively unexplored. We first show that groups of Lie type cannot prove ω = 2 within the group-theoretic approach. This is based on a representation-theoretic argument that identifies the second-smallest dimension of an irreducible representation of a group as a key parameter that determines its viability in this framework. Our proof builds on Gowers' result concerning product-free sets in quasirandom groups. We then give another barrier that rules out certain natural matrix group constructions that make use of subgroups that are far from being self-normalizing. Our barrier results leave open several natural paths to obtain ω = 2 via matrix groups. To explore these routes we propose working in the continuous setting of Lie groups, in which we develop an analogous theory. Obtaining the analogue of ω = 2 in this potentially easier setting is a key challenge that represents an intermediate goal short of actually proving ω = 2. We give two constructions in the continuous setting, each of which evades one of our two barriers.
Cite as

Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, and Chris Umans. Matrix Multiplication via Matrix Groups. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{blasiak_et_al:LIPIcs.ITCS.2023.19,
  author =	{Blasiak, Jonah and Cohn, Henry and Grochow, Joshua A. and Pratt, Kevin and Umans, Chris},
  title =	{{Matrix Multiplication via Matrix Groups}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.19},
  URN =		{urn:nbn:de:0030-drops-175226},
  doi =		{10.4230/LIPIcs.ITCS.2023.19},
  annote =	{Keywords: Fast matrix multiplication, representation theory, matrix groups}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.16
On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors

Authors: Joshua A. Grochow and Youming Qiao

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
In this paper we study some classical complexity-theoretic questions regarding Group Isomorphism (GpI). We focus on p-groups (groups of prime power order) with odd p, which are believed to be a bottleneck case for GpI, and work in the model of matrix groups over finite fields. Our main results are as follows. - Although search-to-decision and counting-to-decision reductions have been known for over four decades for Graph Isomorphism (GI), they had remained open for GpI, explicitly asked by Arvind & Torán (Bull. EATCS, 2005). Extending methods from Tensor Isomorphism (Grochow & Qiao, ITCS 2021), we show moderately exponential-time such reductions within p-groups of class 2 and exponent p. - Despite the widely held belief that p-groups of class 2 and exponent p are the hardest cases of GpI, there was no reduction to these groups from any larger class of groups. Again using methods from Tensor Isomorphism (ibid.), we show the first such reduction, namely from isomorphism testing of p-groups of "small" class and exponent p to those of class two and exponent p. For the first results, our main innovation is to develop linear-algebraic analogues of classical graph coloring gadgets, a key technique in studying the structural complexity of GI. Unlike the graph coloring gadgets, which support restricting to various subgroups of the symmetric group, the problems we study require restricting to various subgroups of the general linear group, which entails significantly different and more complicated gadgets. The analysis of one of our gadgets relies on a classical result from group theory regarding random generation of classical groups (Kantor & Lubotzky, Geom. Dedicata, 1990). For the nilpotency class reduction, we combine a runtime analysis of the Lazard Correspondence with Tensor Isomorphism-completeness results (Grochow & Qiao, ibid.).
Cite as

Joshua A. Grochow and Youming Qiao. On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 16:1-16:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grochow_et_al:LIPIcs.CCC.2021.16,
  author =	{Grochow, Joshua A. and Qiao, Youming},
  title =	{{On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{16:1--16:38},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.16},
  URN =		{urn:nbn:de:0030-drops-142905},
  doi =		{10.4230/LIPIcs.CCC.2021.16},
  annote =	{Keywords: group isomorphism, search-to-decision reduction, counting-to-decision reduction, nilpotent group isomorphism, p-group isomorphism, tensor isomorphism}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.38
Average-Case Algorithms for Testing Isomorphism of Polynomials, Algebras, and Multilinear Forms

Authors: Joshua A. Grochow, Youming Qiao, and Gang Tang

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
We study the problems of testing isomorphism of polynomials, algebras, and multilinear forms. Our first main results are average-case algorithms for these problems. For example, we develop an algorithm that takes two cubic forms f, g ∈ 𝔽_q[x_1, … , x_n], and decides whether f and g are isomorphic in time q^O(n) for most f. This average-case setting has direct practical implications, having been studied in multivariate cryptography since the 1990s. Our second result concerns the complexity of testing equivalence of alternating trilinear forms. This problem is of interest in both mathematics and cryptography. We show that this problem is polynomial-time equivalent to testing equivalence of symmetric trilinear forms, by showing that they are both Tensor Isomorphism-complete (Grochow & Qiao, ITCS 2021), therefore is equivalent to testing isomorphism of cubic forms over most fields.
Cite as

Joshua A. Grochow, Youming Qiao, and Gang Tang. Average-Case Algorithms for Testing Isomorphism of Polynomials, Algebras, and Multilinear Forms. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grochow_et_al:LIPIcs.STACS.2021.38,
  author =	{Grochow, Joshua A. and Qiao, Youming and Tang, Gang},
  title =	{{Average-Case Algorithms for Testing Isomorphism of Polynomials, Algebras, and Multilinear Forms}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.38},
  URN =		{urn:nbn:de:0030-drops-136836},
  doi =		{10.4230/LIPIcs.STACS.2021.38},
  annote =	{Keywords: polynomial isomorphism, trilinear form equivalence, algebra isomorphism, average-case algorithms, tensor isomorphism complete, symmetric and alternating bilinear maps}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.31
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness

Authors: Joshua A. Grochow and Youming Qiao

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We study the complexity of isomorphism problems for tensors, groups, and polynomials. These problems have been studied in multivariate cryptography, machine learning, quantum information, and computational group theory. We show that these problems are all polynomial-time equivalent, creating bridges between problems traditionally studied in myriad research areas. This prompts us to define the complexity class TI, namely problems that reduce to the Tensor Isomorphism (TI) problem in polynomial time. Our main technical result is a polynomial-time reduction from d-tensor isomorphism to 3-tensor isomorphism. In the context of quantum information, this result gives multipartite-to-tripartite entanglement transformation procedure, that preserves equivalence under stochastic local operations and classical communication (SLOCC).
Cite as

Joshua A. Grochow and Youming Qiao. On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grochow_et_al:LIPIcs.ITCS.2021.31,
  author =	{Grochow, Joshua A. and Qiao, Youming},
  title =	{{On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{31:1--31:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.31},
  URN =		{urn:nbn:de:0030-drops-135702},
  doi =		{10.4230/LIPIcs.ITCS.2021.31},
  annote =	{Keywords: complexity class, tensor isomorphism, polynomial isomorphism, group isomorphism, stochastic local operations and classical communication}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.43
Computational Topology and the Unique Games Conjecture

Authors: Joshua A. Grochow and Jamie Tucker-Foltz

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Covering spaces of graphs have long been useful for studying expanders (as "graph lifts") and unique games (as the "label-extended graph"). In this paper we advocate for the thesis that there is a much deeper relationship between computational topology and the Unique Games Conjecture. Our starting point is Linial's 2005 observation that the only known problems whose inapproximability is equivalent to the Unique Games Conjecture - Unique Games and Max-2Lin - are instances of Maximum Section of a Covering Space on graphs. We then observe that the reduction between these two problems (Khot-Kindler-Mossel-O'Donnell, FOCS '04; SICOMP '07) gives a well-defined map of covering spaces. We further prove that inapproximability for Maximum Section of a Covering Space on (cell decompositions of) closed 2-manifolds is also equivalent to the Unique Games Conjecture. This gives the first new "Unique Games-complete" problem in over a decade. Our results partially settle an open question of Chen and Freedman (SODA, 2010; Disc. Comput. Geom., 2011) from computational topology, by showing that their question is almost equivalent to the Unique Games Conjecture. (The main difference is that they ask for inapproximability over Z_2, and we show Unique Games-completeness over Z_k for large k.) This equivalence comes from the fact that when the structure group G of the covering space is Abelian - or more generally for principal G-bundles - Maximum Section of a G-Covering Space is the same as the well-studied problem of 1-Homology Localization. Although our most technically demanding result is an application of Unique Games to computational topology, we hope that our observations on the topological nature of the Unique Games Conjecture will lead to applications of algebraic topology to the Unique Games Conjecture in the future.
Cite as

Joshua A. Grochow and Jamie Tucker-Foltz. Computational Topology and the Unique Games Conjecture. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grochow_et_al:LIPIcs.SoCG.2018.43,
  author =	{Grochow, Joshua A. and Tucker-Foltz, Jamie},
  title =	{{Computational Topology and the Unique Games Conjecture}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.43},
  URN =		{urn:nbn:de:0030-drops-87566},
  doi =		{10.4230/LIPIcs.SoCG.2018.43},
  annote =	{Keywords: Unique Games Conjecture, homology localization, inapproximability, computational topology, graph lift, covering graph, permutation voltage graph, cell}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.20
Minimum Circuit Size, Graph Isomorphism, and Related Problems

Authors: Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions from supposedly-intractable problems to MCSP / MKTP hinged on the power of MCSP / MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of Graph Isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include Linear Code Equivalence, Permutation Group Conjugacy, and Matrix Subspace Conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.
Cite as

Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan. Minimum Circuit Size, Graph Isomorphism, and Related Problems. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.ITCS.2018.20,
  author =	{Allender, Eric and Grochow, Joshua A. and van Melkebeek, Dieter and Moore, Cristopher and Morgan, Andrew},
  title =	{{Minimum Circuit Size, Graph Isomorphism, and Related Problems}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.20},
  URN =		{urn:nbn:de:0030-drops-83455},
  doi =		{10.4230/LIPIcs.ITCS.2018.20},
  annote =	{Keywords: Reductions between NP-intermediate problems, Graph Isomorphism, Minimum Circuit Size Problem, time-bounded Kolmogorov complexity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.34
Boundaries of VP and VNP

Authors: Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
One fundamental question in the context of the geometric complexity theory approach to the VP vs. VNP conjecture is whether VP = !VP, where VP is the class of families of polynomials that can be computed by arithmetic circuits of polynomial degree and size, and VP is the class of families of polynomials that can be approximated infinitesimally closely by arithmetic circuits of polynomial degree and size. The goal of this article is to study the conjecture in (Mulmuley, FOCS 2012) that !VP is not contained in VP. Towards that end, we introduce three degenerations of VP (i.e., sets of points in VP), namely the stable degeneration Stable-VP, the Newton degeneration Newton-VP, and the p-definable one-parameter degeneration VP*. We also introduce analogous degenerations of VNP. We show that Stable-VP subseteq Newton-VP subseteq VP* subseteq VNP, and Stable-VNP = Newton-VNP = VNP* = VNP. The three notions of degenerations and the proof of this result shed light on the problem of separating VP from VP. Although we do not yet construct explicit candidates for the polynomial families in !VP\VP, we prove results which tell us where not to look for such families. Specifically, we demonstrate that the families in Newton-VP \VP based on semi-invariants of quivers would have to be nongeneric by showing that, for many finite quivers (including some wild ones), Newton degeneration of any generic semi-invariant can be computed by a circuit of polynomial size. We also show that the Newton degenerations of perfect matching Pfaffians, monotone arithmetic circuits over the reals, and Schur polynomials have polynomial-size circuits.
Cite as

Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. Boundaries of VP and VNP. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{grochow_et_al:LIPIcs.ICALP.2016.34,
  author =	{Grochow, Joshua A. and Mulmuley, Ketan D. and Qiao, Youming},
  title =	{{Boundaries of VP and VNP}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.34},
  URN =		{urn:nbn:de:0030-drops-63147},
  doi =		{10.4230/LIPIcs.ICALP.2016.34},
  annote =	{Keywords: geometric complexity theory, arithmetic circuit, border complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact